package com.jdaw.datastructure.sparsearray;

public class SparseArray {
    //二维数组转稀疏数组
    public int[][] parseToSparse(int[][] array){
        int col=0,row=0;
        for(int i=0;i<array.length;i++){
            for (int j=0;j<array[i].length;j++){
                array[i][j]=0;
                col++;
            }
        }
        row=array.length;
        int sum=0;
        for(int i=0;i<array.length;i++){
            for (int j=0;j<array[i].length;j++){
                if(array[i][j]!=0){
                    sum++;
                }
            }
        }
        int[][] sparseArray=new int[sum+1][3];
        sparseArray[0][0]=row;
        sparseArray[0][1]=col;
        sparseArray[0][2]=sum;
        int count=1;
        for(int i=0;i<array.length;i++){
            for (int j=0;j<array[i].length;j++){
                if(array[i][j]!=0){
                    sparseArray[count][0]=i;
                    sparseArray[count][1]=j;
                    sparseArray[count][2]=array[i][j];
                    count++;
                }
            }
        }
        return sparseArray;
    }

    //稀疏数组恢复为二维
    public int[][] fromSparse(int[][] sparseArray){
        int col=0,row=0;
        row=sparseArray[0][0];
        col=sparseArray[0][1];
        int[][] array=new int[row][col];
        for(int i=1;i<sparseArray.length;i++){
            array[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];
        }
        return array;

    }

    public static void main(String[] args) {
        int[][] sparseArray=new int[3][3];
        sparseArray[0][0]=11;
        sparseArray[0][1]=11;
        sparseArray[0][2]=2;
        sparseArray[1][0]=1;
        sparseArray[1][1]=2;
        sparseArray[1][2]=1;
        sparseArray[2][0]=2;
        sparseArray[2][1]=3;
        sparseArray[2][2]=2;
        int col=0,row=0;
        row=sparseArray[0][0];
        col=sparseArray[0][1];
        int[][] array=new int[row][col];
        for(int i=1;i<sparseArray.length;i++){
            array[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];
        }
        for(int i=0;i<array.length;i++){
            for (int j=0;j<array[i].length;j++){
                System.out.print(array[i][j]);
                System.out.print(" ");
            }
            System.out.println("");
        }
    }
}
